#include "graph.h"
#include <time.h>
#include <math.h>
#include <limits.h>

#ifdef _OPENMP
#include <omp.h>
#endif

// ========================================================================
// 核心图操作实现
// ========================================================================

Graph* create_graph(int num_nodes, int num_edges) {
    Graph* g = malloc(sizeof(Graph));
    if (!g) return NULL;
    
    g->num_nodes = num_nodes;
    g->num_edges = num_edges;
    
    // 分配节点数组
    g->nodes = malloc(num_nodes * sizeof(GraphNode));
    g->in_degrees = calloc(num_nodes, sizeof(int));
    g->out_degrees = calloc(num_nodes, sizeof(int));
    
    // 分配邻接表
    g->adj_list = malloc(num_nodes * sizeof(int*));
    g->adj_list_sizes = calloc(num_nodes, sizeof(int));
    for (int i = 0; i < num_nodes; i++) {
        g->adj_list[i] = malloc(num_nodes * sizeof(int)); // 最坏情况
    }
    
    // 分配邻接矩阵
    g->adj_matrix = malloc(num_nodes * sizeof(bool*));
    g->is_ancestor = malloc(num_nodes * sizeof(bool*));
    for (int i = 0; i < num_nodes; i++) {
        g->adj_matrix[i] = calloc(num_nodes, sizeof(bool));
        g->is_ancestor[i] = calloc(num_nodes, sizeof(bool));
    }
    
    return g;
}

void free_graph(Graph* g) {
    if (!g) return;
    
    // 释放节点数组中的动态分配字段
    if (g->nodes) {
        for (int i = 0; i < g->num_nodes; i++) {
            if (g->nodes[i].bufs) {
                free(g->nodes[i].bufs);
            }
        }
        free(g->nodes);
    }
    
    free(g->in_degrees);
    free(g->out_degrees);
    free(g->adj_list_sizes);
    
    if (g->adj_list) {
        for (int i = 0; i < g->num_nodes; i++) {
            free(g->adj_list[i]);
        }
        free(g->adj_list);
    }
    
    if (g->adj_matrix) {
        for (int i = 0; i < g->num_nodes; i++) {
            free(g->adj_matrix[i]);
        }
        free(g->adj_matrix);
    }
    
    if (g->is_ancestor) {
        for (int i = 0; i < g->num_nodes; i++) {
            free(g->is_ancestor[i]);
        }
        free(g->is_ancestor);
    }
    
    free(g);
}

void add_edge(Graph* g, int from, int to) {
    if (from >= g->num_nodes || to >= g->num_nodes) return;
    
    // 添加到邻接表
    g->adj_list[from][g->adj_list_sizes[from]++] = to;
    
    // 更新邻接矩阵
    g->adj_matrix[from][to] = true;
    
    // 更新度数
    g->out_degrees[from]++;
    g->in_degrees[to]++;
}

// Floyd-Warshall算法计算传递闭包
void compute_transitive_closure(Graph* g) {
    int n = g->num_nodes;
    
    // 初始化：直接连接的节点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->is_ancestor[i][j] = g->adj_matrix[i][j];
        }
    }
    
    // Floyd-Warshall核心算法
    for (int k = 0; k < n; k++) {
        #ifdef _OPENMP
        #pragma omp parallel for
        #endif
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g->is_ancestor[i][j] = g->is_ancestor[i][j] || 
                    (g->is_ancestor[i][k] && g->is_ancestor[k][j]);
            }
        }
    }
}

// ========================================================================
// 调度操作实现
// ========================================================================

Schedule* create_schedule(int length) {
    Schedule* s = malloc(sizeof(Schedule));
    if (!s) return NULL;
    
    s->length = length;
    s->schedule = malloc(length * sizeof(int));
    s->vstay_history = malloc(length * sizeof(int));
    s->max_vstay = 0;
    
    return s;
}

void free_schedule(Schedule* s) {
    if (!s) return;
    free(s->schedule);
    free(s->vstay_history);
    free(s);
}

// 对应MATLAB的 generate_l0_constrained_schedule 函数
Schedule* generate_initial_schedule(Graph* g) {
    int n = g->num_nodes;
    Schedule* s = create_schedule(n);
    if (!s) return NULL;
    
    // 复制入度数组（用于Kahn拓扑排序）
    int* in_deg_copy = malloc(n * sizeof(int));
    memcpy(in_deg_copy, g->in_degrees, n * sizeof(int));
    
    // 找到所有入度为0的节点作为ready_list
    int* ready_list = malloc(n * sizeof(int));
    int ready_count = 0;
    
    for (int i = 0; i < n; i++) {
        if (in_deg_copy[i] == 0) {
            ready_list[ready_count++] = i;
        }
    }
    
    // L0存储器状态跟踪 [L0A, L0B, L0C]
    int l0_active[3] = {0, 0, 0};
    int scheduled_count = 0;
    
    // 主调度循环
    while (scheduled_count < n) {
        int node_to_schedule = -1;
        int node_idx_in_ready = -1;
        
        // 寻找可调度的节点（满足L0约束）
        for (int i = 0; i < ready_count; i++) {
            int node_id = ready_list[i];
            GraphNode* node = &g->nodes[node_id];
            bool is_schedulable = true;
            
            // 检查L0约束
            if (node->op_code == OP_ALLOC) {
                if (node->type_code == TYPE_L0A && l0_active[0] > 0) is_schedulable = false;
                if (node->type_code == TYPE_L0B && l0_active[1] > 0) is_schedulable = false;
                if (node->type_code == TYPE_L0C && l0_active[2] > 0) is_schedulable = false;
            }
            
            if (is_schedulable) {
                node_to_schedule = node_id;
                node_idx_in_ready = i;
                break;
            }
        }
        
        if (node_to_schedule == -1) {
            printf("错误：调度死锁！\n");
            free(in_deg_copy);
            free(ready_list);
            free_schedule(s);
            return NULL;
        }
        
        // 从ready_list中移除已选择的节点
        for (int i = node_idx_in_ready; i < ready_count - 1; i++) {
            ready_list[i] = ready_list[i + 1];
        }
        ready_count--;
        
        // 添加到调度序列
        s->schedule[scheduled_count++] = node_to_schedule;
        
        // 更新L0状态
        GraphNode* node = &g->nodes[node_to_schedule];
        if (node->op_code == OP_ALLOC) {
            if (node->type_code == TYPE_L0A) l0_active[0]++;
            if (node->type_code == TYPE_L0B) l0_active[1]++;
            if (node->type_code == TYPE_L0C) l0_active[2]++;
        } else if (node->op_code == OP_FREE) {
            if (node->type_code == TYPE_L0A) l0_active[0]--;
            if (node->type_code == TYPE_L0B) l0_active[1]--;
            if (node->type_code == TYPE_L0C) l0_active[2]--;
        }
        
        // 更新后继节点的入度
        for (int i = 0; i < g->adj_list_sizes[node_to_schedule]; i++) {
            int succ = g->adj_list[node_to_schedule][i];
            in_deg_copy[succ]--;
            if (in_deg_copy[succ] == 0) {
                ready_list[ready_count++] = succ;
            }
        }
    }
    
    // 计算目标函数值
    s->max_vstay = calculate_max_vstay(s->schedule, s->length, g, s->vstay_history);
    
    free(in_deg_copy);
    free(ready_list);
    return s;
}

// 对应MATLAB的 is_l0_schedule_valid 函数 (与MATLAB版本保持一致)
bool is_l0_schedule_valid(const int* schedule, int length, const Graph* g) {
    int l0_active[3] = {0, 0, 0}; // [L0A, L0B, L0C]
    
    for (int i = 0; i < length; i++) {
        int node_id = schedule[i];
        const GraphNode* node = &g->nodes[node_id];
        
        if (node->op_code == OP_ALLOC) {
            // L0约束检查 (与MATLAB版本完全一致)
            if (node->type_code == TYPE_L0A) l0_active[0]++;
            if (node->type_code == TYPE_L0B) l0_active[1]++;
            if (node->type_code == TYPE_L0C) l0_active[2]++;
            
            // 检查是否违反L0约束（每种L0类型最多1个同时活跃）
            if (l0_active[0] > 1 || l0_active[1] > 1 || l0_active[2] > 1) {
                return false;
            }
            
        } else if (node->op_code == OP_FREE) {
            // L0约束更新
            if (node->type_code == TYPE_L0A) l0_active[0]--;
            if (node->type_code == TYPE_L0B) l0_active[1]--;
            if (node->type_code == TYPE_L0C) l0_active[2]--;
        }
    }
    
    return true;
}

// 全局统计变量（可选，用于性能测试）
static long long topo_check_count = 0;
static long long topo_comparison_count = 0;

// 拓扑依赖检查函数 (优化版：采用MATLAB高效算法)
bool is_topological_valid(const int* schedule, int length, const Graph* g) {
    topo_check_count++; // 统计调用次数
    // 创建节点位置映射：node_id -> position_in_schedule
    int* node_positions = malloc(g->num_nodes * sizeof(int));
    if (!node_positions) {
        return false; // 内存分配失败
    }
    
    // 初始化位置映射 (未在schedule中的节点位置为-1)
    for (int i = 0; i < g->num_nodes; i++) {
        node_positions[i] = -1;
    }
    for (int i = 0; i < length; i++) {
        node_positions[schedule[i]] = i;
    }
    
    // 【优化算法】对每个节点u，只检查其后代节点
    for (int u = 0; u < g->num_nodes; u++) {
        int pos_u = node_positions[u];
        if (pos_u == -1) continue; // u不在schedule中，跳过
        
        // 遍历所有可能的后代节点v
        for (int v = 0; v < g->num_nodes; v++) {
            // 只检查u是v祖先的情况
            if (g->is_ancestor[u][v]) {
                topo_comparison_count++; // 统计有效比较次数
                int pos_v = node_positions[v];
                if (pos_v == -1) continue; // v不在schedule中，跳过
                
                // 检查依赖约束：祖先u必须在后代v之前执行
                if (pos_u >= pos_v) {
                    // 发现拓扑违规：祖先在后代之后或同时执行
                    free(node_positions);
                    return false;
                }
            }
        }
    }
    
    free(node_positions);
    return true;
}

// 性能统计输出函数
void print_topological_check_stats(void) {
    printf("\n=== 拓扑检查性能统计 ===\n");
    printf("总调用次数: %d\n", (int)topo_check_count);
    printf("有效比较次数: %d\n", (int)topo_comparison_count);
    if (topo_check_count > 0) {
        printf("平均每次调用比较次数: %.2f\n", (double)topo_comparison_count / topo_check_count);
    }
    printf("==========================\n");
}

// 重置性能统计
void reset_topological_check_stats(void) {
    topo_check_count = 0;
    topo_comparison_count = 0;
}

// 综合调度合法性检查函数 (L0约束 + 拓扑依赖)
bool is_schedule_fully_valid(const int* schedule, int length, const Graph* g) {
    return is_l0_schedule_valid(schedule, length, g) && 
           is_topological_valid(schedule, length, g);
}

// 对应MATLAB的 calculate_max_vstay 函数
int calculate_max_vstay(const int* schedule, int length, const Graph* g, int* history) {
    int v_stay = 0;
    int max_v = 0;
    bool has_invalid_state = false;
    
    for (int i = 0; i < length; i++) {
        int node_id = schedule[i];
        const GraphNode* node = &g->nodes[node_id];
        
        // 只考虑L1和UB类型的内存占用
        if (node->type_code == TYPE_L1 || node->type_code == TYPE_UB) {
            if (node->op_code == OP_ALLOC) {
                v_stay += node->size;
            } else if (node->op_code == OP_FREE) {
                v_stay -= node->size;
                // 检测无效状态：释放超过已分配的内存
                if (v_stay < 0) {
                    has_invalid_state = true;
                    // 对于无效调度，返回惩罚值
                    if (history) {
                        for (int j = 0; j <= i; j++) {
                            history[j] = INT_MAX;
                        }
                    }
                    return INT_MAX; // 返回最大值作为惩罚
                }
            }
        }
        
        // 更新最大值
        if (v_stay > max_v) {
            max_v = v_stay;
        }
        
        if (history) {
            history[i] = v_stay;
        }
    }
    
    return max_v;
}

// ========================================================================
// 工具函数实现
// ========================================================================

void print_graph_stats(const Graph* g) {
    printf("图统计信息:\n");
    printf("  节点数: %d\n", g->num_nodes);
    printf("  边数: %d\n", g->num_edges);
    
    // 统计不同类型的节点
    int op_count[7] = {0};
    int type_count[7] = {0};
    
    for (int i = 0; i < g->num_nodes; i++) {
        op_count[g->nodes[i].op_code]++;
        type_count[g->nodes[i].type_code]++;
    }
    
    printf("  操作类型分布: ALLOC=%d, FREE=%d, 其他=%d\n", 
           op_count[OP_ALLOC], op_count[OP_FREE], 
           g->num_nodes - op_count[OP_ALLOC] - op_count[OP_FREE]);
    printf("  数据类型分布: L1=%d, UB=%d, L0A=%d, L0B=%d, L0C=%d\n",
           type_count[TYPE_L1], type_count[TYPE_UB], 
           type_count[TYPE_L0A], type_count[TYPE_L0B], type_count[TYPE_L0C]);
}

void print_schedule_stats(const Schedule* s) {
    printf("调度统计信息:\n");
    printf("  调度长度: %d\n", s->length);
    printf("  峰值内存占用: %d\n", s->max_vstay);
}

double get_time_seconds(void) {
    return (double)clock() / CLOCKS_PER_SEC;
}

// ========================================================================
// MATLAB等价函数实现
// ========================================================================

// 对应MATLAB的 successors(G, node) 函数
int* get_successors(const Graph* g, int node_id, int* count) {
    if (!g || node_id < 0 || node_id >= g->num_nodes || !count) {
        if (count) *count = 0;
        return NULL;
    }
    
    *count = g->adj_list_sizes[node_id];
    
    if (*count == 0) {
        return NULL;
    }
    
    // 分配内存并复制后继节点列表
    int* successors = malloc(*count * sizeof(int));
    if (!successors) {
        *count = 0;
        return NULL;
    }
    
    memcpy(successors, g->adj_list[node_id], *count * sizeof(int));
    return successors;
}

// 对应MATLAB的 predecessors(G, node) 函数
int* get_predecessors(const Graph* g, int node_id, int* count) {
    if (!g || node_id < 0 || node_id >= g->num_nodes || !count) {
        if (count) *count = 0;
        return NULL;
    }
    
    // 遍历所有节点，找到以node_id为后继的节点
    int* temp_predecessors = malloc(g->num_nodes * sizeof(int));
    *count = 0;
    
    for (int i = 0; i < g->num_nodes; i++) {
        // 检查节点i是否有指向node_id的边
        for (int j = 0; j < g->adj_list_sizes[i]; j++) {
            if (g->adj_list[i][j] == node_id) {
                temp_predecessors[(*count)++] = i;
                break; // 每个节点最多只会是一次前驱
            }
        }
    }
    
    if (*count == 0) {
        free(temp_predecessors);
        return NULL;
    }
    
    // 分配精确大小的内存
    int* predecessors = malloc(*count * sizeof(int));
    memcpy(predecessors, temp_predecessors, *count * sizeof(int));
    free(temp_predecessors);
    
    return predecessors;
}

// 释放节点列表内存
void free_node_list(int* node_list) {
    free(node_list);
}

// ========================================================================
// 传递闭包验证函数
// ========================================================================

// 将传递闭包矩阵输出到文件，便于与MATLAB对比
void print_transitive_closure(const Graph* g, const char* filename) {
    FILE* fp = fopen(filename, "w");
    if (!fp) {
        printf("无法创建传递闭包输出文件: %s\n", filename);
        return;
    }
    
    fprintf(fp, "C语言传递闭包矩阵 (is_ancestor)\n");
    fprintf(fp, "矩阵大小: %d x %d\n", g->num_nodes, g->num_nodes);
    fprintf(fp, "格式: is_ancestor[i][j] = 1 表示节点i是节点j的祖先\n\n");
    
    // 输出列标题
    fprintf(fp, "     ");
    for (int j = 0; j < g->num_nodes; j++) {
        fprintf(fp, "%3d", j);
    }
    fprintf(fp, "\n");
    
    // 输出矩阵内容
    for (int i = 0; i < g->num_nodes; i++) {
        fprintf(fp, "%3d: ", i);
        for (int j = 0; j < g->num_nodes; j++) {
            fprintf(fp, "%3d", g->is_ancestor[i][j] ? 1 : 0);
        }
        fprintf(fp, "\n");
    }
    
    // 输出统计信息
    int total_edges = 0;
    int self_loops = 0;
    for (int i = 0; i < g->num_nodes; i++) {
        for (int j = 0; j < g->num_nodes; j++) {
            if (g->is_ancestor[i][j]) {
                total_edges++;
                if (i == j) self_loops++;
            }
        }
    }
    
    fprintf(fp, "\n统计信息:\n");
    fprintf(fp, "传递闭包中的边数: %d\n", total_edges);
    fprintf(fp, "自环数量: %d\n", self_loops);
    fprintf(fp, "密度: %.4f\n", (double)total_edges / (g->num_nodes * g->num_nodes));
    
    fclose(fp);
    printf("传递闭包矩阵已输出到: %s\n", filename);
}

// 验证传递闭包的正确性
void verify_transitive_closure(const Graph* g) {
    printf("正在验证传递闭包的正确性...\n");
    
    int errors = 0;
    
    // 1. 验证原始边是否都包含在传递闭包中
    for (int i = 0; i < g->num_nodes; i++) {
        for (int j = 0; j < g->adj_list_sizes[i]; j++) {
            int target = g->adj_list[i][j];
            if (!g->is_ancestor[i][target]) {
                printf("错误：原始边 %d -> %d 不在传递闭包中\n", i, target);
                errors++;
            }
        }
    }
    
    // 2. 验证传递性：如果 i->k 且 k->j，则必须有 i->j
    for (int i = 0; i < g->num_nodes; i++) {
        for (int k = 0; k < g->num_nodes; k++) {
            for (int j = 0; j < g->num_nodes; j++) {
                if (g->is_ancestor[i][k] && g->is_ancestor[k][j] && !g->is_ancestor[i][j]) {
                    printf("错误：传递性违反 %d -> %d -> %d，但 %d 不能到达 %d\n", 
                           i, k, j, i, j);
                    errors++;
                    if (errors > 10) goto check_done; // 避免输出过多错误
                }
            }
        }
    }
    
check_done:
    if (errors == 0) {
        printf("✅ 传递闭包验证通过！\n");
    } else {
        printf("❌ 传递闭包验证失败，发现 %d 个错误\n", errors);
    }
    
    // 输出一些统计信息
    int reachable_pairs = 0;
    for (int i = 0; i < g->num_nodes; i++) {
        for (int j = 0; j < g->num_nodes; j++) {
            if (g->is_ancestor[i][j]) {
                reachable_pairs++;
            }
        }
    }
    
    printf("传递闭包统计：\n");
    printf("  可达节点对数量: %d / %d\n", reachable_pairs, g->num_nodes * g->num_nodes);
    printf("  图连通密度: %.2f%%\n", 100.0 * reachable_pairs / (g->num_nodes * g->num_nodes));
}
